#!/usr/bin/python
# Filename: Search.py

# Average Search Length:
# is average compare times to find a target record
# is criteria to evaluate search algorithm

# Linear Search:
# max(SL) = n
# fail(SL) = n(or n+1 if there is a PH)
# ASL when successful: (1+n)/2
# ASL: (1+n)/2*p + (n+1)*q = (1+n)/2*p + (n+1)*(1-p) = (n+1)*(1-p/2)

# Binary Search:
# max(SL) = upper(log(2)(n+1)), eg. 7 nodes balanced binary tree's max(ASL) = 3
# fail(SL) = upper(log(2)(n+1)), when the tree is approximate balanced
# ASL when successful: (1*1 + 2*2 + 3*4 + ... + log(n+1)*(n+1)/2)/(1+2+4+...(n+1)/2), is about log(n+1)-1, !!!but I can't prove it
# ASL: (log(n+1)-1)*p + log(n+1)(1-p) = log(n+1) - p, they're approximately same

# Block Search:
# sorted blocks, linear with no order inner block
# an index is need to tell the largest key in each block, length of each block and reference to that block
# the index is in order
# ASL = ASL(index) + ASL(block)
# assume using linear search in index and block
# ASL = (b+1)/2 + (s+1)/2 = (b+s)/2 + 1 = (bs+s^2)/2s + 1 = (n+s^2)/2s + 1
# when s = sqrt(n), min(ASL) = sqrt(n)+1 is approximately sqrt(n)
# if blocks are in external memory, I/O will also increase time cost 
# assume using binary search in index and linear in block
# ASL = log(b+1)-1 + (s+1)/2 is about log(1+n/s) + s/2
# so how to select s is a trade-off, pay attention to s = 1 and s = n
# when block sizes difference increasing, the efficiency decreasing

# Set Search:
# when values are gathered in a range as whole set
# eg. find odd prime number between 1 to 15
# odd number: 1, 3, 5, 7, 9, 11, 13, 15
# prime number: 2, 3, 5, 7, 11, 13
# intersection: 3, 5, 7, 11, 13
# bit-operation can be used for intersection and union

# Hash:
# cannot be used when search a range of record
# also cannot be used when different records have same key
# conceptions: load factor, conflict, synonym
# 2 key problems: equality of load location, how to deal with conflict
# when records increasing, load factor increasing beyond 1/2, efficiency of hash will decrease greatly

# Hash Functions:
# 1) mod: select a proper prime number as denominator
# a) if use 2^n or 10^n as denominator, then result will only depend on right n bits/digits
# b) potential disadvantage is continuous keys are mapped to continuous addresses, which may cause performance problems
# 2) multiply on the remainder then get the integer part
# a) hash(key) = lower(n*(A*key%1))
# b) if address has p bit/digit, then n = 2^p/10^p, address is the left most n bit/digit of the remainder
# c) Knuth suggest to use A = (5^(1/2)-1)/2 which is golden section in common, and best A is decided by array's charactor
# 3) square and select bits/digits
# a) square keys to enlarge their difference, then select partial bits/digits to compose the address
# 4) digit analysis
# a) if key is composed by n d-digits numbers and each number in a range of values(r)
# b) select numbers which are equal distributed in load location, to compose the address
# c) distribution E(k)(a(k,i)-E(a(k,i))/r)^2: E is accumulation, a(k,i) presents ith number in r occurs a time in kth number in n
# d) the less E(k) is, the equaler it distributes in kth number
# e) disadvantage is that keys distribution must be known before compose the hash function, if keys modified, function must change
# 5) radix transform
# a) assume the key is on other radix, eg. assume 123 decimal is 123 on 13, which is (123)13 = (198)10
# b) select partial digits as address
# c) new radix should be large than original, and they're relatively-prime
# 6) folden
# a) when key has many digits, divide them into several groups with same size, then fold them together to compose the address
# b) 2 ways of folding: move and fold / straight fold
# 7) ELF Hash
# a) Executable and Linking Format in UNIX V4.0

# Deal with Conflict
# open hashing: store synonym out of hash table
# 1) link
# a) there is a reference to a link in each slot of hash table, when conflict, add record to the end of this link(or sort the link nodes)
# 2) overflow area / static link
# a) an area beside hash table, each slot of hash table can have reference to a node in this area
# b) each node in this area can have reference to another node, which composes the link
# c) synonym is stored in this area as well as in the link
# 3) bucket
# a) when the table and link is too large to store in the memory, they should be stored in external memory
# b) hash table can be divided into several pages, it's called directory
# c) each slot of hash table is a bucket, with reference to a link of pages, which stores synonyms
# d) search: bucket id = hash(key), then search the record in the bucket, page by page
# e) modify:
# e.1) modify the key value: remove and add
# e.2) modify without changing key value: search and modify
# f) add: bucket id = hash(key), add record to bucket(may need to create new page)
# g) remove: search and mark it as removed/move last record of page to that position, when a page is empty, release it
# h) when records increasing, hash table may need to rebuild(change hash function, or enlarge directory)
# closed hashing: store synonym in another table slot
# there should be a detecting strategy(detecting sequence) to find where to store the synonym
# !!!when removing a record, it can't be really deleted, just mark it as deleted, this called tombstone
# 1) linear detection
# a) every slot(if step is proper) can be used to store synonym
# b) may cause clustering -> cause long time detecting
# 2) square detection: 1^2, -1^2, 2^2, -2^2, ...
# 3) pseudo-random number(PRN) detection
# 4) dua hash detection
# can solve secondary clustering(synonym shares same detecting sequence will cause clustering)
# a) detecting sequence is function of both slot id and key
# b) when slot(hash1(key)) is used, detect hash2(key), 2*hash2(key), ...
# c) disadvantage: more complex computation

def binary_search(array, value, cmp=cmp):
    '''input array must be already in order'''
    left = 0
    right = len(array)-1

    def search(array, value, left, right, cmp):
        record = (left+right)/2
        if cmp(array[record], value) == 0: return record
        # this is not necessary
        if cmp(value, array[left]) < 0 or cmp(value, array[right]) > 0: return -1
        if cmp(value, array[record]) < 0:
            if left == record: return -1
            else: return search(array, value, left, record-1, cmp)
        else:
            if right == record: return -1
            else: return search(array, value, record+1, right, cmp)

    return search(array, value, left, right, cmp)
    pass

def block_search(array, cmp=cmp):
    pass

def elf_hash(string):
    h = 0
    for key in string:
        h = (h << 4) + ord(key)
        g = h & 0xF0000000
        if g: h ^= g >> 24
        h &= ~g
    return h

class dictionary:
    pass

if __name__ == "__main__":
    
    def test_binary_search():
        l= [1, 3, 4, 6, 8, 10, 11, 12, 15, 20]
        print "3 in l:", binary_search(l, 3)
        print "5 in l:", binary_search(l, 5)
        print "10 in l:", binary_search(l, 10)
        print "20 in l:", binary_search(l, 20)
        print "30 in l:", binary_search(l, 30)

    def test_elf_hash():
        s1 = "I'm a student of Peking University"
        s2 = "I'm a student of PKU"
        print "elf of %s is:" % s1, elf_hash(s1)
        print "elf of %s is:" % s2, elf_hash(s2)

    test_binary_search()
    test_elf_hash()
